Supply Chain Chaos 📉
Ships are arriving in a scrambled order. We need to calculate the Índice de Caos (number of inversions) to optimize the AI traffic controller.
¿Qué es una Inversión?
A pair of indices $(i, j)$ is an inversion if:
- $i < j$ (El barco $i$ llega antes que $j$)
- $A[i] > A[j]$ (El barco $i$ tiene un ID de prioridad más alto)
Analysis 🔍
Secuencia de Ejemplo: [2, 4, 1, 3, 5]
- ❌ (2, 1): 2 llega antes que 1, pero 2 > 1
- ❌ (4, 1): 4 llega antes que 1, pero 4 > 1
- ❌ (4, 3): 4 llega antes que 3, pero 4 > 3
- Caos Total: 3 Inversiones
El Desafío
A brute force nested loop is $O(N^2)$.
for i in range(n):
for j in range(i+1, n): ...
for j in range(i+1, n): ...
For $N=100,000$, this takes ~10 billion ops. Resultado: Superado el límite de tiempo.